package 力扣_树算法.遍历.层序遍历扩展;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**662. 二叉树最大宽度
 * @author zx
 * @create 2022-04-11 15:45
 * 关于完全二叉树的节点编号
 * 若根节点从1开始编号,设父节点的编号为K,则左子树2K,右子树为2K + 1
 */
public class 二叉树最大宽度_662 {
    /**
     * @return 层序遍历
     */
    public int widthOfBinaryTree2(TreeNode root) {
        int res = 0;
        if(root == null){
            return res;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        //用集合保存节点编号
        //每一个操作都如影随形,保证一一对应
        Deque<Integer> index = new ArrayDeque<>();
        queue.offer(root);
        index.offer(1);
        while(!queue.isEmpty()){
            int levelCount = queue.size();
            res = Math.max(res,index.peekLast() - index.peekFirst() + 1);
            for(int i = 0;i < levelCount;i++){
                TreeNode node = queue.poll();
                int k = index.poll();
                if(node.left != null){
                    queue.offer(node.left);
                    index.offer(2 * k);
                }
                if(node.right != null){
                    queue.offer(node.right);
                    index.offer(2 * k + 1);
                }
            }
        }
        return res;
    }

    /**
     * @return bit
     */
    public int widthOfBinaryTree(TreeNode root) {
        // 在实际操作过程中，层序遍历时存储每个节点和他的编号
        // 当每一层遍历结束，取出最左侧的节点编号L和最右侧的节点编号R
        // 该层的宽度就是R - L + 1
        if(root == null){
            return 0;
        }
        int maxWidth = 0;
        Queue<NodeWithNum> queue = new LinkedList<>();
        queue.offer(new NodeWithNum(root,1));
        while(!queue.isEmpty()){
            int levelWidth = 0;
            //最左侧的节点编号
            int L = 0;
            //最右侧的节点编号
            int R = 0;
            int size = queue.size();
            for(int i = 0;i < size;i++){
                NodeWithNum cur = queue.poll();
                if(i == 0){
                    //node就是最左侧节点
                    L = cur.num;
                }
                if(i == size - 1){
                    //此时node就是该层的最后侧节点
                    R = cur.num;
                }
                if(cur.node.left != null){
                    queue.offer(new NodeWithNum(cur.node.left,cur.num * 2));
                }
                if(cur.node.right != null){
                    queue.offer(new NodeWithNum(cur.node.right,cur.num * 2 + 1));
                }
            }
            levelWidth = R - L + 1;
            maxWidth = Math.max(levelWidth,maxWidth);
        }
        return maxWidth;
    }
    //此时在层序遍历的过程中会存储每个出现的节点和它的编号,创建一个新的类
    //将TreeNode二次包装,新增一个该节点的值
    private class NodeWithNum{
        //具体每个二叉树的节点
        TreeNode node;
        //该节点的编号
        int num;
        public NodeWithNum(TreeNode node,int num){
            this.node = node;
            this.num = num;
        }
    }
}